package swardToOffer.struct_6_bit_operation;

/**
 * @Author ChanZany
 * @Date 2021/5/20 21:59
 * @Version 1.0
 * // 面试题16：数值的整数次方
 * // 题目：实现函数double Power(double base, int exponent)，求base的exponent
 * // 次方。不得使用库函数，同时不需要考虑大数问题。
 * 思路，当exponent(n)为偶数时，f(a,n) = f(a,n/2)*f(a,n/2)
 * f(a,n/2)=f(a,n/4)*f(a,n/4)
 * 为奇数时，f(a,n) = a* f(a,(n-1)/2)*f(a,(n-1)/2)
 */
public class Power {

    private double solution(double a, int n) {
        if (n == 0) return 1;
        if (n == 1) return a;
        if (a <= 0) throw new RuntimeException("a cannot be a negative number or 0");
        double result = solution(a, n >> 1); //f(a,n/2)
        result *= result; //f(a,n)
        if (n % 2 != 0) result *= a;
        return result;
    }

    public static void main(String[] args) {
        System.out.println(new Power().solution(3, 5));
    }

}
